// 2025/3/21
// https://leetcode.cn/problems/search-insert-position/description/?envType=study-plan-v2&envId=top-100-liked
// 搜索插入位置

class Solution {
    public:
        int searchInsert(vector<int>& nums, int target) {
            int left = 0, right = nums.size();
            int mid = (left + right) / 2;
            while(left < right)
            {
                if(nums[mid] > target)
                    right = mid - 1;
                else if(nums[mid] < target)
                    left = mid + 1;
                else
                    break;
                mid = (left + right) / 2;
            }
            if(mid < nums.size() && nums[mid] < target)
                mid++;
            return mid;
        }
    };